#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
using namespace std;

typedef vector<vector<bool>> BVV;

char const *longestPalindrome(char const *s) {
    int len = strlen(s);
    int mid;
    int mlp = 0;
    int clp;
    int ps, pe;
    int ms = 0;
    for(mid=0; mid<len-mlp/2; mid++) {
        //以mid为中心
        clp = 1;
        ps = mid-1; pe = mid+1;
        while(ps>=0 && pe<len){
            if(s[ps] == s[pe]) {
                clp += 2; 
                ps--; pe++;
            } else {
                break;
            }      
        }
        if(clp > mlp) {
            mlp = clp;
            ms = ps+1;
        }
        //以..mid为左半侧
        ps = mid; pe = mid+1;
        clp = 0;
        while(ps>=0 && pe<len) {
            if(s[ps] == s[pe]) {
                clp += 2; 
                ps--; pe++;
            } else {
                break;
            }      
        }
        if(clp > mlp) {
            mlp = clp;
            ms = ps+1;
        }
    }
    if(mlp > 0) {
        return strndup(s+ms, mlp);
    }else {
        return NULL;
    }
}

char const *longestPalindrome2(char const *s) {
    int len = strlen(s);
    /******************
    *dp[i][j]: s[i..j]是否为回文
    *dp[i][j] = {
    *   if i>=j
            true
        else 
            s[i]==s[j] && dp[i+1][j-1]
    *}
    ******************/
    BVV dp(len);
    int i;
    for(i=0; i<len; i++) {
        dp[i].resize(len);
        dp[i][i] = true;
    }
    for(i=1; i<len; i++) {
        dp[i][i-1] = true;
    }
    int gap, j;
    int mlp = 0;
    int ms = 0;
    for(gap = 1; gap < len; gap++) {
        for(i=0; i+gap<len; i++) {
            j = i+gap;
            dp[i][j] = dp[i+1][j-1] && s[i] == s[j];
            if(dp[i][j]) {
                mlp = gap+1;
                ms = i;
            }
        }
    }
    
    if(mlp > 0) {
        return strndup(s+ms, mlp);
    }else {
        return NULL;
    }
    
}
int main(void) {
    char const *s =  "1aibohphobia";
    char const *lp = NULL;
    
    lp = longestPalindrome(s);
    printf("最长回文子串：\n\t%s\n", lp);
    printf("\t长度：%d\n", (int)strlen(lp));
    free((void*)lp);
    
    lp = longestPalindrome(s);
    printf("最长回文子串：\n\t%s\n", lp);
    printf("\t长度：%d\n", (int)strlen(lp));
    free((void*)lp);

    return 0;
}

